package other;

/**
 * 动态规划，一般是求问题的最优解，分割为子问题，求得就是子问题最优解，子问题最优解组成了最终问题的最优解 自顶向下，子问题的重复计算太多，影响效率，例如fibonacci
 * 自下向上，子问题的最优解可以复用
 *
 *
 * 割绳子问题的思路 假设一个绳子的长度为n，该绳子切成若干段的最优解为f（n），假设第一次切掉的长度为i 则 f（n）=max（f（i）f（n-i) 初始的情况 如果绳子的长度小于2，没法切
 * 返回0 如果绳子的长度为2 f(2)=max{f(1)f(1))}=1 如果绳子的长度为3 f(3)=max{f(1)f(2),f(1)f(1)f(1)}=2 如果绳子的长度为4
 * f(4)=max{f(1)f(3),f(2)f(2)} 如果绳子的长度为5 f(5)=max{f(1)f(4),f(2)f(3)}
 *
 * f(1)=1 f(2)=1 f(3)=1
 */
public class CutRope {


  public int cutRope(int n) {
    if (n < 0) {
      throw new RuntimeException("n应大于0");
    }

    if (n == 1) {
      return 1;
    }
    if (n == 2) {
      return 1;
    }
    if (n == 3) {
      return 2;
    }

    int[] array = new int[n + 1];
    //初始化的值是用于计算的值
    array[0] = 0;
    array[1] = 1;
    array[2] = 2;
    array[3] = 3;

    //后序的值是保存的最优解 1-3的最优解在最顶上已经判断了  最优解是从4开始的

    for (int i = 4; i <= n; i++) {
      int max = 0;
      for (int j = 1; j <= (i / 2); j++) { //避免重复的计算
        int temp = array[j] * array[i - j];
        if (max < temp) {
          max = temp;
        }
      }
      array[i] = max;
    }
    return array[n];

  }

  public static void main(String args[]) {
    CutRope cutRope = new CutRope();
    System.out.println(cutRope.cutRope(8));
  }

}
